Prime numbers have many applications in applied mathematics. As is generally understood by those skilled in the arts of mathematics and applied mathematics, a prime number is a natural number greater than 1 having no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number.
Around 300 BC, the Greek mathematician Euclid demonstrated that there are infinitely many primes. There is no known useful formula that sets apart all of the prime numbers from composites. However, the statistical behavior of primes can be modelled. For example, the prime number theorem, proven at the end of the 19th century, says that the probability that a given, randomly chosen number n is prime is inversely proportional to its number of digits, or to the logarithm of n.
Until recently, number theory in general, and the study of prime numbers in particular, was seen as the canonical example of pure mathematics, with no applications outside of the self-interest of studying the topic. This changed in the 1970's with the development of the use of prime numbers as a basis for the creation of public key cryptography algorithms.
RSA is one of the first practicable public-key cryptosystems and is widely used for secure data transmission. In such a cryptosystem, the encryption key is public and differs from the decryption key which is kept secret. In RSA, this asymmetry is based on the practical difficulty of factoring the product of two large prime numbers. A user of RSA creates and then publishes the product of two large prime numbers, along with an auxiliary value, as their public key. The prime factors must be kept secret. Anyone can use the public key to encrypt a message, but with currently published methods, if the public key is large enough, only someone with knowledge of the prime factors can feasibly decode the message.
More recently, in the field of computing, prime numbers have been used for hash tables and pseudorandom number generators. A hash table (also hash map) is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the correct value can be found. Ideally, the hash function assigns each key to a unique bucket, but this situation is rarely achievable in practice (usually some keys will hash to the same bucket). Instead, most hash table designs assume that hash collisions—different keys that are assigned by the hash function to the same bucket—will occur and must be accommodated in some way.
A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers that approximates the properties of random numbers. In terms of random number generation, the sequence is not truly random in that it is completely determined by a relatively small set of initial values, called the PRNG's state, which includes a truly random seed. Although sequences that are closer to truly random can be generated using hardware random number generators, pseudorandom numbers are important in practice for their speed in number generation and their reproducibility. PRNGs are central in applications such as simulations (e.g. of physical systems via the Monte Carlo method), in procedural generation, and in cryptography.
It is within this context that aspects of the present disclosure arise.